UVa/11665 - Chinese Ink/11665.cpp

   1 // Accepted
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 #define EPS 1e-9
  29
  30 typedef pair<int, int> point;
  31 typedef vector< point > polygon;
  32
  33 vector< polygon > polygons;
  34
  35 const int MAXN = 50;
  36 int p[MAXN];
  37
  38 int find(int u) {
  39     return p[u] == u ? u : p[u] = find(p[u]);
  40 }
  41
  42 void link(int u, int v) {
  43     if (find(u) != find(v)) {
  44         p[find(u)] = find(v);
  45     }
  46 }
  47
  48 // Polar angle
  49 // Returns an angle in the range [0, 2*Pi) of a given Cartesian point.
  50 // If the point is (0,0), -1.0 is returned.
  51 // REQUIRES:
  52 // include math.h
  53 // define EPS 0.000000001, or your choice
  54 // P has members x and y.
  55 double polarAngle( point p ) {
  56     double x = p.first, y = p.second;
  57     if(fabs(x) <= EPS && fabs(y) <= EPS) return -1.0;
  58     if(fabs(x) <= EPS) return (y > EPS ? 1.0 : 3.0) * acos(0);
  59     double theta = atan(1.0 * y / x);
  60     if(x > EPS) return(y >= -EPS ? theta : (4*acos(0) + theta));
  61     return(2 * acos( 0 ) + theta);
  62 }
  63
  64 //Point inside polygon
  65 // Returns true iff p is inside poly.
  66 // PRE: The vertices of poly are ordered (either clockwise or
  67 //      counter-clockwise.
  68 // POST: Modify code inside to handle the special case of "on
  69 // an edge".
  70 // REQUIRES:
  71 // polarAngle()
  72 // include math.h
  73 // include vector
  74 // define EPS 0.000000001, or your choice
  75 bool pointInPoly( point p, const polygon &poly ) {
  76   int n = poly.size();
  77   double ang = 0.0;
  78   for(int i = n - 1, j = 0; j < n; i = j++){
  79     point v( poly[i].first - p.first, poly[i].second - p.second );
  80     point w( poly[j].first - p.first, poly[j].second - p.second );
  81     double va = polarAngle(v);
  82     double wa = polarAngle(w);
  83     double xx = wa - va;
  84     if(va < -0.5 || wa < -0.5 || fabs(fabs(xx)-2*acos(0)) < EPS){
  85         // POINT IS ON THE EDGE
  86         return true;
  87         assert( false );
  88         ang += 2 * acos( 0 );
  89         continue;
  90       }
  91     if( xx < -2 * acos( 0 ) ) ang += xx + 4 * acos( 0 );
  92     else if( xx > 2 * acos( 0 ) ) ang += xx - 4 * acos( 0 );
  93     else ang += xx;
  94   }
  95   return( ang * ang > 1.0 );
  96 }
  97
  98
  99 /*
 100   Returns true if point (x, y) lies inside (or in the border)
 101   of box defined by points (x0, y0) and (x1, y1).
 102 */
 103 bool point_in_box(double x, double y,
 104                   double x0, double y0,
 105                   double x1, double y1){
 106   return
 107     min(x0, x1) <= x && x <= max(x0, x1) &&
 108     min(y0, y1) <= y && y <= max(y0, y1);
 109 }
 110
 111 /*
 112   Finds the intersection between two segments (Not infinite
 113   lines!)
 114   Segment 1 goes from point (x0, y0) to (x1, y1).
 115   Segment 2 goes from point (x2, y2) to (x3, y3).
 116
 117   (Can be modified to find the intersection between a segment
 118   and a line)
 119
 120   Handles the case when the 2 segments are:
 121   *Parallel but don't lie on the same line (No intersection)
 122   *Parallel and both lie on the same line (Infinite
 123   *intersections or no intersections)
 124   *Not parallel (One intersection or no intersections)
 125
 126   Returns true if the segments do intersect in any case.
 127 */
 128 bool segment_segment_intersection(double x0, double y0,
 129                                   double x1, double y1,
 130
 131                                   double x2, double y2,
 132                                   double x3, double y3){
 133   double t0 = (y3-y2)*(x0-x2)-(x3-x2)*(y0-y2);
 134   double t1 = (x1-x0)*(y2-y0)-(y1-y0)*(x2-x0);
 135   double det = (y1-y0)*(x3-x2)-(y3-y2)*(x1-x0);
 136   if (fabs(det) < EPS){
 137     //parallel
 138     if (fabs(t0) < EPS || fabs(t1) < EPS){
 139       //they lie on same line, but they may or may not intersect.
 140       return (point_in_box(x0, y0,   x2, y2, x3, y3) ||
 141               point_in_box(x1, y1,   x2, y2, x3, y3) ||
 142               point_in_box(x2, y2,   x0, y0, x1, y1) ||
 143               point_in_box(x3, y3,   x0, y0, x1, y1));
 144     }else{
 145       //just parallel, no intersection
 146       return false;
 147     }
 148   }else{
 149     t0 /= det;
 150     t1 /= det;
 151     /*
 152       0 <= t0 <= 1 iff the intersection point lies in segment 1.
 153       0 <= t1 <= 1 iff the intersection point lies in segment 2.
 154     */
 155     if (0.0 <= t0 && t0 <= 1.0 && 0.0 <= t1 && t1 <= 1.0){
 156       double x = x0 + t0*(x1-x0);
 157       double y = y0 + t0*(y1-y0);
 158       //intersection is point (x, y)
 159       return true;
 160     }
 161     //the intersection points doesn't lie on both segments.
 162     return false;
 163   }
 164 }
 165
 166
 167
 168
 169 bool polygonsIntersect(const polygon &a, const polygon &b) {
 170     int na = a.size(), nb = b.size();
 171     for (int i = 0; i < na; ++i) {
 172         if (pointInPoly(a[i], b)) return true;
 173     }
 174     for (int i = 0; i < nb; ++i) {
 175         if (pointInPoly(b[i], a)) return true;
 176     }
 177
 178     for (int i = 0; i < na; ++i) {
 179         for (int j = 0; j < nb; ++j) {
 180             int xa1 = a[i].first, ya1 = a[i].second;
 181             int xa2 = a[(i + 1) % na].first, ya2 = a[(i + 1) % na].second;
 182             int xb1 = b[j].first, yb1 = b[j].second;
 183             int xb2 = b[(j + 1) % nb].first, yb2 = b[(j + 1) % nb].second;
 184             if (segment_segment_intersection(xa1, ya1,    xa2, ya2,               xb1, yb1, xb2, yb2)) {
 185                 return true;
 186             }
 187         }
 188     }
 189
 190
 191     return false;
 192 }
 193
 194
 195 void solve() {
 196     int n = polygons.size();
 197     for (int i = 0; i < n; ++i) {
 198         p[i] = i;
 199     }
 200
 201     for (int i = 0; i < n; ++i) {
 202         for (int j = i + 1; j < n; ++j) {
 203             if (polygonsIntersect(polygons[i], polygons[j])) {
 204                 link(i, j);
 205             }
 206         }
 207     }
 208     set<int> ans;
 209     for (int i = 0; i < n; ++i) {
 210         ans.insert(find(i));
 211     }
 212     cout << ans.size() << endl;
 213 }
 214
 215
 216 int main(){
 217     int n;
 218     while (cin >> n) {
 219         if (n == 0) break;
 220         string s; getline(cin, s);
 221         polygons.clear();
 222         for (int i = 0; i < n; ++i){
 223             polygons.push_back(polygon());
 224             getline(cin, s);
 225             stringstream sin(s);
 226             int x, y;
 227             while (sin >> x >> y) {
 228                 polygons.back().push_back(point(x, y));
 229             }
 230             assert(polygons.back().size() >= 3);
 231         }
 232         assert(polygons.size() == n);
 233
 234         solve();
 235     }
 236     return 0;
 237 }